package com.leetcode.q3;

import java.util.HashMap;

/**
 * <p> description: desc</p>
 *
 * @author tanzc
 * @date 2022/3/29
 **/
public class LengthOfLongestSubstring {
    // leetcode官方题解
    // 这个题解最重要的地方在于使用hashMap把每个字符上次出现位置存储，
    // 再次遍历到该字符时，把长度计算起始位置一道字符上次出现的后一位
    // 同时，将字符本次位置更新进hashMap ---> 这个是精髓 --> 这样，滑动窗口时，可以保证窗口内始终没有重复字符
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        // 计算长度的左边位置
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                // 更新left，滑动窗口至重复字符的下一位置
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            // i - left + 1 即为当前字符向前的最大长度
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    /**
     * 这个是最基础的遍历找法了
     * 原理也是滑动窗口，但是只对窗口边界的字符做重复判断，当窗口内部有重复后，无法及时调整窗口位置，导致结果不正确
     * 改进方法是：每次判断左右边界字符后，同时对内部字符和右边界字符做一次判断，如果内部字符和右边界字符重复，
     * 需要调整左边界至内部重复字符下一位置
     * 改进方法将会加大时间复杂度，因此，使用hashMap来记录每个字符位置，并判断是否有重复字符就很块，并且窗口位置调整更快
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstringMe(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        int x = 0, y = 1;
        int l = 1, max = -1;
        while (y < s.length()) {
            if (s.charAt(x) == s.charAt(y)) {
                if (x == y) {
                    y++;
                } else {
                    x++;
                }
            } else {
                // 此处需判断窗口内部字符与右边界字符是否重复
                // 如有重复，需修改x值
                int xx = x + 1;
                while (xx < y) {
                    if (s.charAt(xx) == s.charAt(y)) {
                        x = xx + 1;
                        break;
                    } else {
                        xx++;
                    }
                }
                // 改进结束
                l = y - x + 1;
                y++;
            }
            if (l > max) {
                max = l;
            }
        }
        return max;
    }
}
